package leetcode.median;

public class $97_IsInterleave {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int t = s3.length();
        if (m + n != t) {
            return false;
        }
        // dp[i][j] 表示s1的前i个元素和s2的前j个元素能否组成s3的前i + j个元素
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0;i <= m;i++) {
            for (int j = 0;j <= n;j++) {
                // s1 aabcc
                // s2 dbbca
                // s3 aadbbcbcac
                int p = i + j - 1;
                if (i > 0) {
                    // s3的第i + j - 1个字符从s1出
                    dp[i][j] = s1.charAt(i - 1) == s3.charAt(p) && dp[i - 1][j];
                }
                if (j > 0) {
                    // s3的第i + j - 1个字符从s2出
                    dp[i][j] = dp[i][j] || (s2.charAt(j - 1) == s3.charAt(p) && dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
